#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <string>

//class Solution {
//public:
//    vector<vector<bool>> visit;
//    int m, n;
//    bool exist(vector<vector<char>>& board, string word) {
//        m = board.size();
//        n = board[0].size();
//        visit.resize(board.size());
//        for (int i = 0; i < visit.size(); i++)
//        {
//            visit[i].resize(board[0].size(), true);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    visit[i][j] = false;
//                    if (dfs(board, i, j, word, 1))
//                        return true;
//                    visit[i][j] = true;
//                }
//            }
//        }
//        return false;
//    }
//    bool check(vector<vector<char>>& board, int i, int j)
//    {
//        return (i >= 0 && i < board.size()) && (j >= 0 && j < board[0].size());
//    }
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
//    {
//        if (pos == word.size())
//            return true;
//
//        for (int l = 0; l < 4; l++)
//        {
//            int x = i + dx[l];
//            int y = j + dy[l];
//            if (check(board, x, y) && visit[x][y] && board[x][y] == word[pos])
//            {
//                visit[x][y] = false;
//                if (dfs(board, x, y, word, pos + 1))
//                    return true;
//                visit[x][y] = true;
//            }
//        }
//        return false;
//    }
//};
//class Solution {
//public:
//    vector<string> path;
//    int len = 0;
//    bool ret = false;
//    int j = 0;
//    bool exist(vector<vector<char>>& board, string word) {
//        dfs(board, word, 0, 0);
//        return ret;
//    }
//    void dfs(vector<vector<char>>& board, string& word, int row, int j)
//    {
//        if (row == board.size())
//        {
//            return;
//        }
//        if (row != 0 && board[row][len] != word[j])
//            return;
//        for (int i = len; i < board[0].size(); i++)
//        {
//            if (board[row][i] == word[j])
//            {
//                j++;
//                dfs(board, word, row + 1, j);
//            }
//            else
//            {
//                if (row == 0)
//                    j = 0;
//            }
//        }
//        for (int i = len - 1; i >= 0; i--)
//        {
//            if (board[row][i] == word[j])
//            {
//                j++;
//                dfs(board, word, row + 1, j);
//            }
//            else
//            {
//                break;
//            }
//        }
//        if (j == word.size())
//        {
//            ret = true;
//        }
//        dfs(board, word, row + 1, j);
//    }
//};
//class Solution {
//public:
//    vector<vector<bool>> visit;
//    int m;
//    int n;
//    int ret = 0;
//    int getMaximumGold(vector<vector<int>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        visit.resize(m);
//        for (int i = 0; i < m; i++)
//        {
//            visit[i].resize(n, true);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 0)
//                    visit[i][j] = false;
//            }
//        }
//
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (visit[i][j])
//                {
//                    visit[i][j] = false;
//                    int ret1 = dfs(grid, i, j);
//                    visit[i][j] = true;
//                    if (ret1 > ret)
//                        ret = ret1;
//                }
//            }
//        }
//        return ret;
//    }
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int dfs(vector<vector<int>>& grid, int i, int j)
//    {
//        int ret1 = grid[i][j];
//        for (int l = 0; l < 4; l++)
//        {
//            int x = i + dx[l], y = j + dy[l];
//            if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y])
//            {
//                visit[i][j] = false;
//                int ret2 = dfs(grid, x, y) + grid[i][j];
//                visit[i][j] = true;
//                if (ret2 > ret1)
//                    ret1 = ret2;
//            }
//        }
//        return ret1;
//    }
//};

class Solution {
public:
    int path = 0;
    int m, n;
    vector<vector<bool>> visit;
    int count;
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        count = m * n;
        visit.resize(m);
        for (int i = 0; i < m; i++)
            visit[i].resize(n, true);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == -1)
                {
                    visit[i][j] = false;
                    count--;
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    count--;
                    visit[i][j] = false;
                    dfs(grid, i, j, 0);
                    visit[i][j] = true;
                    break;
                }
            }
        }
        return path;
    }
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    void dfs(vector<vector<int>>& grid, int i, int j, int step)
    {
        if (grid[i][j] == 2)
        {
            if (step == count)
                path++;
            return;
        }
        for (int l = 0; l < 4; l++)
        {
            int x = i + dx[l], y = j + dy[l];
            if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y])
            {
                visit[x][y] = false;
                dfs(grid, x, y, step + 1);
                visit[x][y] = true;
            }
        }
    }
};
int main()
{
    Solution s;
    //vector<vector<char>> board = { {'A','B','C','E'} ,{'S','F','C','S'},{'A','D','E','E'}};
    //string word = "ABCCED";
    vector<vector<int>> grid = { {1,0,0,0} ,{0,0,0,0},{0,0,2,-1} };
    s.uniquePathsIII(grid);
  /*  int ret = s.getMaximumGold(grid);*/
    //cout << ret << endl;
    //s.exist(board, word);
    return 0;
}